//Given two strings s and p, return an array of all the start indices of p's 
//anagrams in s. You may return the answer in any order. 
//
// An Anagram is a word or phrase formed by rearranging the letters of a 
//different word or phrase, typically using all the original letters exactly once. 
//
// 
// Example 1: 
//
// 
//Input: s = "cbaebabacd", p = "abc"
//Output: [0,6]
//Explanation:
//The substring with start index = 0 is "cba", which is an anagram of "abc".
//The substring with start index = 6 is "bac", which is an anagram of "abc".
// 
//
// Example 2: 
//
// 
//Input: s = "abab", p = "ab"
//Output: [0,1,2]
//Explanation:
//The substring with start index = 0 is "ab", which is an anagram of "ab".
//The substring with start index = 1 is "ba", which is an anagram of "ab".
//The substring with start index = 2 is "ab", which is an anagram of "ab".
// 
//
// 
// Constraints: 
//
// 
// 1 <= s.length, p.length <= 3 * 10⁴ 
// s and p consist of lowercase English letters. 
// 
// Related Topics Hash Table String Sliding Window 👍 5226 👎 215


package leetcode.editor.en;

import java.util.ArrayList;
import java.util.List;

public class _438_FindAllAnagramsInAString {
    public static void main(String[] args) {
        Solution solution = new _438_FindAllAnagramsInAString().new Solution();
        List<Integer> anagrams = solution.findAnagrams("cbaebabacd", "abc");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> r = new ArrayList<>();
            int pL = p.length();
            int sL = s.length();
            if (sL < pL) {
                return r;
            }
            int[] a = new int[26];
            int[] b = new int[26];
            for (int i = 0; i < pL; i++) {
                a[p.charAt(i)-'a']++;
            }
            int left=0;
            for (int right = 0; right < sL; right++) {
                int curRight = s.charAt(right) - 'a';
                b[curRight]++;
                while (b[curRight]>a[curRight]){
                    int curLeft = s.charAt(left) - 'a';
                    b[curLeft]--;
                    left++;
                }
                if (right-left+1== pL){
                    r.add(left);
                }
            }
            return r;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}